// 刀砍毒杀怪兽问题
// 怪兽的初始血量是一个整数hp，给出每一回合刀砍和毒杀的数值cuts和poisons
// 第i回合如果用刀砍，怪兽在这回合会直接损失cuts[i]的血，不再有后续效果
// 第i回合如果用毒杀，怪兽在这回合不会损失血量，但是之后每回合都损失poisons[i]的血量
// 并且你选择的所有毒杀效果，在之后的回合都会叠加
// 两个数组cuts、poisons，长度都是n，代表你一共可以进行n回合
// 每一回合你只能选择刀砍或者毒杀中的一个动作
// 如果你在n个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
// 但是怪兽如果有中毒效果的话，那么怪兽依然会在血量耗尽的那回合死掉
// 返回至少多少回合，怪兽会死掉
// 数据范围 :
// 1 <= n <= 10^5
// 1 <= hp <= 10^9
// 1 <= cuts[i]、poisons[i] <= 10^9
// 本题来自真实大厂笔试，找不到测试链接，所以用对数器验证

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <ctime>

using namespace std;

// 不做要求
// i ：当前来到的位置，将在这个位置做出选择（砍一刀或者选毒）
// r : 怪兽的剩余血量
// p : 中毒效果
// 函数的返回值是让怪兽死掉，至少要多少回合
int f1(vector<int>& cuts, vector<int>& poisons, int i, int r, int p, vector<vector<vector<int>>>& dp)
{
    r -= p;
    if (r <= 0) return i + 1;

    if (i == cuts.size())
    {
        // 在 n 个回合内没有直接杀死怪兽，意味着你已经无法有新的行动了
        if (p == 0) return INT_MAX; // 如果此时没有中毒效果，则无法杀死怪兽，返回无穷大
        else return cuts.size() + 1 + (r + p - 1) / p;
    }

    if (dp[i][r][p] != 0) return dp[i][r][p];

    // 本回合选砍一刀，如果这一刀能将怪兽砍死，则直接返回
    int p1 = r <= cuts[i] ? (i + 1) : f1(cuts, poisons, i + 1, r - cuts[i], p, dp);
    // 本回合选毒
    int p2 = f1(cuts, poisons, i + 1, r, p + poisons[i], dp);
    int ans = min(p1, p2);
    dp[i][r][p] = ans;
    return ans;
}

// 动态规划方法(只是为了验证)
// 目前没有讲动态规划，所以不需要理解这个函数
// 这个函数只是为了验证二分答案的方法是否正确的
// 纯粹为了写对数器验证才设计的方法，血量比较大的时候会超时
// 这个方法不做要求，此时并不需要理解，可以在学习完动态规划章节之后来看看这个函数
int fast1(vector<int>& cuts, vector<int>& poisons, int hp)
{
    int sum = 0;
    for (int num : poisons)
    {
        sum += num;
    }
    vector<vector<vector<int>>> dp(cuts.size(), vector<vector<int>>(hp + 1, vector<int>(sum + 1, 0)));
    return f1(cuts, poisons, 0, hp, 0, dp);
}


// cuts、posions，每一回合刀砍、毒杀的效果
// hp：怪兽血量
// limit：回合的限制
bool f(vector<int>& cuts, vector<int>& poisons, long hp, int limit)
{
    int n = min((int)cuts.size(), limit);
    for (int i = 0, j = 1; i < n; i++, j++)
    {
        hp -= max((long)cuts[i], (long)(limit - j) * (long)poisons[i]);
        if (hp <= 0)
        {
            return true;
        }
    }
    return false;
}

// 二分答案法
// 最优解
// 时间复杂度 O(n * log(hp))，额外空间复杂度 O(1)
int fast2(vector<int>& cuts, vector<int>& poisons, int hp)
{
    int ans = INT_MAX;
    for (int l = 1, r = hp + 1, m; l <= r;)
    {
        m = l + ((r - l) >> 1);
        if (f(cuts, poisons, hp, m))
        {
            ans = m;
            r = m - 1;
        }
        else l = m + 1;
    }
    return ans;
}

vector<int> randomArray(int n, int v)
{
    vector<int> ans(n);
    for (int i = 0; i < n; i++)
    {
        ans[i] = rand() % v + 1;
    }
    return ans;
}

int main()
{
    srand(time(nullptr));
    cout << "测试开始" << endl;
    int N = 30;
    int V = 20;
    int H = 300;
    int testTimes = 10000;
    for (int i = 0; i < testTimes; i++)
    {
        int n = rand() % N + 1;
        vector<int>&& cuts = randomArray(n, V);
        vector<int>&& poisons = randomArray(n, V);
        int hp = rand() % H + 1;
        int ans1 = fast1(cuts, poisons, hp);
        int ans2 = fast2(cuts, poisons, hp);
        if (ans1 != ans2)
        {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;
    return 0;
}